#include "ChartBuilder.h"

namespace LSCM
{
	ChartBuilder::ChartBuilder(Mesh* mesh, const std::vector<FeatureSet>& sets)
		: m_mesh(mesh), m_featureSets(sets), m_maxDistance(0.0f)
	{
		const auto numSets = m_featureSets.size();

		// 添加两个属性，分别储存特征值和状态
		m_mesh->add_property(m_chartBoundaries);
		m_mesh->add_property(m_faceStates);

		// 每个面的距离都初始化为零
		for (auto f_it = m_mesh->faces_begin(), f_end = m_mesh->faces_end(); f_it != f_end; f_it++)
			m_mesh->property(m_faceStates, *f_it) = FaceState(*f_it, numSets);
	}

	ChartBuilder::~ChartBuilder()
	{
		// 完成后移除两个属性
		m_mesh->remove_property(m_chartBoundaries);
		m_mesh->remove_property(m_faceStates);
	}

	const std::vector<Chart>& ChartBuilder::Build()
	{
		std::cout << "Building Charts..." << std::endl;

		initializeDistance();
		buildCharts();

		std::cout << "Charts: " << m_charts.size() << std::endl;

		return m_charts;
	}

	bool ChartBuilder::Validate()
	{
		// 检查是否包含了所有面
		for (auto f_it = m_mesh->faces_begin(), f_end = m_mesh->faces_end(); f_it != f_end; f_it++)
		{
			auto& face = *f_it;
			bool contains = false;
			for (auto& c : m_charts)
			{
				if (c.contains(face))
				{
					contains = true;
					break;
				}
			}

			if (!contains)
				return false;
		}

		return true;
	}

	void ChartBuilder::initializeDistance()
	{
		// 获得特征集数，每个特征集有一个边界
		const auto size = m_featureSets.size();
		std::vector<std::vector<Mesh::FaceHandle>> boundaries(size);

		// 初始化边界集
		for (auto i = 0; i < size; i++)
		{
			// 引用特征集和边界
			const auto& featureSet = m_featureSets.at(i);
			auto& boundary = boundaries[i];

			// 遍历每条特征边
			for (const auto& halfedge : featureSet.halfedges())
			{
				Mesh::VertexHandle vertices[2];

				// 获得起始、终止点
				vertices[0] = m_mesh->to_vertex_handle(halfedge);
				vertices[1] = m_mesh->from_vertex_handle(halfedge);

				for (const auto& vertex : vertices)
				{
					// 考虑顶点的相邻面
					for (auto f_it = m_mesh->vf_begin(vertex), f_end = m_mesh->vf_end(vertex); f_it != f_end; f_it++)
					{
						const auto& face = *f_it;

						// 如果这个面不在边界集中，就将其加入
						if (std::find(boundary.begin(), boundary.end(), face) == boundary.end())
						{
							boundary.push_back(face);

							// 记录这个面的状态：到第 i 个特征集的距离为 1
							m_mesh->property(m_faceStates, face).setSetDistance(i, 1);
						}
					}
				}
			}
		}

		// 一开始图表深度是 1，边界边左右各一个面，下一步扩张就得到 2
		int depth = 2;

		// 判定是否修改了边界，循环扩张直到无法修改
		bool modified = true;
		while (modified)
		{
			// 初始化为没有修正
			modified = false;

			// 遍历每个特征集的边界集
			for (auto i = 0; i < boundaries.size(); i++)
			{
				// 考虑其中一个边界集
				auto& boundary = boundaries[i];

				// 存放新边界
				std::vector<Mesh::FaceHandle> newBoundary;
				for (const auto& face : boundary)
				{
					// 判断这个面是否在边界上（这里指它是否在其他边界集扩张的范围内，如果是，就不能扩张到这个面）
					if (m_mesh->property(m_faceStates, face).border())
						continue;

					// 遍历周围的面
					for (auto f_it = m_mesh->ff_begin(face), f_end = m_mesh->ff_end(face); f_it != f_end; f_it++)
					{
						auto& state = m_mesh->property(m_faceStates, *f_it);

						// 如果已经计算出了到当前边界的距离或者已经在边界集中，就跳过
						if (state.hasSetDistance(i) || std::find(boundary.begin(), boundary.end(), *f_it) != boundary.end())
							continue;

						// 获得到当前特征的距离
						state.setSetDistance(i, depth);
						newBoundary.push_back(*f_it);
					}
				}

				// 如果新边界是空的，说明这个边界集扩张到极限，直接清空
				boundary.resize(newBoundary.size());

				// 如果新的边界集不是空的，就修改边界
				if (!newBoundary.empty())
				{
					std::copy(newBoundary.begin(), newBoundary.end(), boundary.begin());
					modified = true;
				}
			}

			// 增加深度
			depth++;
		}

		// 计算每个面到所有特征集的平均距离
		for (auto f_it = m_mesh->faces_begin(), f_end = m_mesh->faces_end(); f_it != f_end; f_it++)
		{
			auto& state = m_mesh->property(m_faceStates, *f_it);
			state.calcDistance();

			// 记录最大平均距离
			m_maxDistance = std::max(m_maxDistance, state.distance());
		}
	}

	void ChartBuilder::initializeSeeds()
	{
		// 比较器，用来比较两个面的距离属性
		auto f_compare = [this](const Mesh::FaceHandle& a, const Mesh::FaceHandle& b) -> bool
		{
			const auto& stateA = m_mesh->property(m_faceStates, a);
			const auto& stateB = m_mesh->property(m_faceStates, b);

			return stateA.distance() < stateB.distance();
		};

		// 处在边界上的面是到所有特征集距离最大的面，将它们按照平均距离由大到小排序
		std::priority_queue<Mesh::FaceHandle, std::vector<Mesh::FaceHandle>, decltype(f_compare)> heap(f_compare);
		for (auto f_it = m_mesh->faces_begin(), f_end = m_mesh->faces_end(); f_it != f_end; f_it++)
			if (m_mesh->property(m_faceStates, *f_it).border())
				heap.push(*f_it);

		// 初始化集合标记
		const auto size = m_featureSets.size();
		std::vector<int> sets(size, 0);

		// 堆中的每个面是一个图表的种子
		while (!heap.empty())
		{
			// 弹出最上面的面（具有最大距离的面）
			auto face = heap.top();
			heap.pop();

			auto& state = m_mesh->property(m_faceStates, face);

			// 如果这个面有一个特征集合 i 没有用过（sets[i] == 0）并且在它的边界上 hasSetDistance(i)
			bool unused = false;
			for (auto i = 0; i < size; i++)
				if (sets[i] == 0 && state.hasSetDistance(i))
					unused = true;

			// 没用过的话
			if (unused)
			{
				// 在“任何特征集”的边界上就对应设为 1，表示它们都用过了这个面
				for (auto i = 0; i < size; i++)
					if (state.hasSetDistance(i))
						sets[i] = 1;

				// 将这个面分配给当前图表（指定索引就是 m_charts 的大小）
				state.setChart(m_charts.size());

				// 创建一个新图表，将这个面和距离信息加入，作为生成种子
				m_charts.emplace_back(Chart());
				m_charts.back().add(face, state.distance());
			}
		}
	}

	void ChartBuilder::buildCharts()
	{
		// 得到了所有图表的种子
		initializeSeeds();

		// 建立一个比较器，比较拥有给定的两个半边的两个面的距离属性
		auto he_compare = [this](const Mesh::HalfedgeHandle& a, const Mesh::HalfedgeHandle& b) -> bool
		{
			const auto& stateA = m_mesh->property(m_faceStates, m_mesh->face_handle(a));
			const auto& stateB = m_mesh->property(m_faceStates, m_mesh->face_handle(b));

			return stateA.distance() < stateB.distance();
		};

		// 加载每个图表上一个面的半边
		std::priority_queue<Mesh::HalfedgeHandle, std::vector<Mesh::HalfedgeHandle>, decltype(he_compare)> heap(he_compare);
		for (const auto& chart : m_charts)
		{
			// 取出图表的种子
			const auto face = chart.faces().front();

			// 遍历面上的所有半边，添加到堆中
			for (auto he_it = m_mesh->fh_begin(face), he_end = m_mesh->fh_end(face); he_it != he_end; he_it++)
				heap.push(*he_it);
		}

		// 所有半边都标记为 1
		for (auto e_it = m_mesh->edges_begin(), e_end = m_mesh->edges_end(); e_it != e_end; e_it++)
			m_mesh->property(m_chartBoundaries, *e_it) = 1;

		// 开始循环扩张图表
		while (!heap.empty())
		{
			auto halfedge = heap.top();
			heap.pop();

			auto edge = m_mesh->edge_handle(halfedge);
			auto face = m_mesh->face_handle(halfedge);
			auto faceOpp = (Mesh::FaceHandle)m_mesh->opposite_face_handle(halfedge);

			// 判断半边左右的两个面是否都有效，即处理边界情况
			if (!face.is_valid() || !faceOpp.is_valid())
				continue;

			auto& state = m_mesh->property(m_faceStates, face);
			auto& stateOpp = m_mesh->property(m_faceStates, faceOpp);

			// 如果 face 没有所属图表，就与 faceOpp 交换
			if (!state.hasChart())
			{
				std::swap(face, faceOpp);
				std::swap(state, stateOpp);
			}

			// 如果 faceOpp 没有所属图表
			if (!stateOpp.hasChart())
			{
				// 获得 face 所属图表，将其加入
				auto& chart = m_charts[state.chart()];

				chart.add(faceOpp, stateOpp.distance());
				stateOpp.setChart(state.chart());

				// 然后可以删除这条边
				removeChartBoundaryEdge(edge);

				// 考虑 faceOpp 上的边
				for (auto e_it = m_mesh->fe_begin(faceOpp), e_end = m_mesh->fe_end(faceOpp); e_it != e_end; e_it++)
				{
					auto e = *e_it;

					// 如果这条边仍然被标记为 1，也就是还没有删除，就记录两条半边
					if (m_mesh->property(m_chartBoundaries, e) > 0)
					{
						heap.push(m_mesh->halfedge_handle(e, 0));
						heap.push(m_mesh->halfedge_handle(e, 1));
					}
				}
			}
			// 如果两个面属于不同的图表，那么检查距离
			else if (state.chart() != stateOpp.chart())
			{
				auto& chart = m_charts[state.chart()];
				auto& chartOpp = m_charts[stateOpp.chart()];

				// 距离阈值，如果两个 chart 之间的距离小于阈值，就会将它们合并
				const auto epsDistance = m_maxDistance / 4;
				if ((chart.maxDistance() - state.distance()) < epsDistance && (chartOpp.maxDistance() - state.distance()) < epsDistance)
					mergeCharts(chart, chartOpp);
			}
		}

		// 将空的图表移动到末端
		auto move = [](const Chart& chart)
		{
			return chart.cleared() || chart.faces().empty();
		};
		auto last = std::remove_if(m_charts.begin(), m_charts.end(), move);

		// 删除第一个空图表到末端之间的空图表
		m_charts.erase(last, m_charts.end());

		// 保存图表顶点
		for (auto& chart : m_charts)
		{
			auto& faces = chart.faces();
			auto& vertices = chart.vertices();
			for (auto& face : faces)
			{
				auto fv_iter = m_mesh->fv_begin(face), fv_end = m_mesh->fv_end(face);
				for (; fv_iter != fv_end; fv_iter++)
					vertices.push_back(*fv_iter);
			}

			// 删除重复顶点
			std::sort(vertices.begin(), vertices.end());
			vertices.erase(std::unique(vertices.begin(), vertices.end()), vertices.end());
		}
	}

	bool ChartBuilder::removeChartBoundaryEdge(Mesh::EdgeHandle edge)
	{
		// 已经被删除就不用删除
		if (m_mesh->property(m_chartBoundaries, edge) == 0)
			return false;

		// 设为零，表示删除边
		m_mesh->property(m_chartBoundaries, edge) = 0;

		// 获得边上的半边
		auto halfedge = m_mesh->halfedge_handle(edge, 0);

		// 获得两个端点
		Mesh::VertexHandle vertices[2];
		vertices[0] = m_mesh->to_vertex_handle(halfedge);
		vertices[1] = m_mesh->from_vertex_handle(halfedge);

		// 查找周围的边，删除没有连接到 2 个其它边界边的边
		// 这个递归过程将会持续进行，直到检查完整个边界边集
		for (const auto& vertex : vertices)
		{
			for (auto e_it = m_mesh->cve_begin(vertex), e_end = m_mesh->cve_end(vertex); e_it != e_end;)
			{
				// 每删除一个这样的边，就回到开头重新遍历，确保全部删除
				if (!checkChartBoundaryEdge(*e_it) && removeChartBoundaryEdge(*e_it))
					e_it = m_mesh->cve_begin(vertex);
				else
					e_it++;
			}
		}

		return true;
	}

	bool ChartBuilder::checkChartBoundaryEdge(Mesh::EdgeHandle edge)
	{
		// 删除的边不属于边界
		if (m_mesh->property(m_chartBoundaries, edge) == 0)
			return false;

		// 获得边上的半边
		auto halfedge = m_mesh->halfedge_handle(edge, 0);

		// 获得两个端点
		Mesh::VertexHandle vertices[2];
		vertices[0] = m_mesh->to_vertex_handle(halfedge);
		vertices[1] = m_mesh->from_vertex_handle(halfedge);

		// 检查当前边连接了多少个其它边界边
		int connections = 0;
		for (const auto& vertex : vertices)
		{
			for (auto e_it = m_mesh->cve_begin(vertex), e_end = m_mesh->cve_end(vertex); e_it != e_end; e_it++)
			{
				// 一旦连接到其它边界边，退出循环
				if (*e_it != edge && m_mesh->property(m_chartBoundaries, *e_it) > 0)
				{
					connections++;
					break;
				}
			}
		}
		// 只有两个顶点，因此 connections = 0, 1, 2

		// 判断连接数是否为 2
		return connections == 2;
	}

	void ChartBuilder::mergeCharts(Chart& chartTo, Chart& chartFrom)
	{
		// 确保合并两个非空图表
		assert(!chartTo.cleared());
		assert(!chartFrom.cleared());

		// 取目标图表的面，获得它所属的图表索引
		const auto& faceRef = chartTo.faces().front();
		auto chartIndex = m_mesh->property(m_faceStates, faceRef).chart();

		// 修改源图表中的面所属的图表
		for (const auto& f : chartFrom.faces())
			m_mesh->property(m_faceStates, f).setChart(chartIndex);

		chartTo.merge(chartFrom);
		chartFrom.clear();
	}
}